/*
2021-7-14
https://www.acwing.com/problem/content/489/
*/

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
typedef pair<int,int> PII;
const int N=65,M=32010;

PII master[N];
vector<PII> servent[N];
int n,m;
int f[M];

int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        int v,p,q;
        cin>>v>>p>>q;
        if(!q) master[i]={v,v*p};
        else servent[q].push_back({v,v*p});
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int u=m;u>=0;u--)
        {
            for(int j=0;j< 1<<servent[i].size();j++)
            {
                int v=master[i].first,w=master[i].second;
                for(int k=0;k<servent[i].size();k++)
                {
                    if(j>>k & 1)
                    {
                        v+=servent[i][k].first;
                        w+=servent[i][k].second;
                    }
                }
                if(u>=v) f[u]=max(f[u],f[u-v]+w);
            }
        }
    }
    cout<<f[m]<<endl;
    
    return 0;
}
